﻿/*
7-6 列出连通集 (25 分)
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:
按照"{ v​1​​  v​2​​  ... v​k​​  }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "MGraph.hpp"
#include "Queue.hpp"
#include "SeqStack.hpp"

#define GMAXSIZE 11
typedef MGraph<int> MGraphT;

struct Cell {
	int r;
	int c;

	Cell() :r(0), c(0) {}
	Cell(int r, int c) :r(r), c(c) {}
};

void build_graph(MGraphT* g) {
	int v0, v1;
	int n, m;
	scanf("%d %d", &n, &m);
	g->size = n;
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &v0, &v1);
		g->addVertex(v0, v1);
	}
	g->dump();
}

void zero_visited(int visited[], int n) {
	for (int i = 0; i < n; i++)
		visited[i] = 0;
}

void DFS(MGraphT* g, int from, int visited[GMAXSIZE]) {
	SeqStack<int> stack(GMAXSIZE);
	Queue<int> queue;
	int cell;

	for (int i = g->size - 1; i >= 0; i--) {
		if (visited[i] || g->at(from, i) < 0)
			continue;
		stack.push(i);
	}
	stack.push(from);
	while (!stack.isEmpty()) {
		stack.pop(cell);
		from = cell;
		if (visited[from])
			continue;
		visited[from] = 1;
		queue.enqueue(from);
		for (int i = g->size - 1; i >= 0; i--) {
			if (visited[i] || g->at(from, i) < 0)
				continue;
			stack.push(i);
		}
	}

	printf("{");
	while (!queue.isEmpty()) {
		printf(" %d", queue.dequeue());
	}
	printf(" }\n");
}

void BFS(MGraphT* g, int from, int visited[GMAXSIZE]) {

	Queue<int> queue;
	int cell;

	queue.enqueue(from);

	printf("{");
	while (!queue.isEmpty()) {
		from = queue.dequeue();
		if (visited[from])
			continue;
		visited[from] = 1;
		printf(" %d", from);
		for (int i = 0; i < g->size; i++) {
			if (visited[i] || g->at(from, i) < 0)
				continue;
			queue.enqueue(i);
		}
	}

	printf(" }\n");
}

void resolve(MGraphT* g) {
	int visited[GMAXSIZE] = { 0 };
	build_graph(g);
	zero_visited(visited, g->size);
	for (int i = 0; i < g->size; i++) {
		if (!visited[i])
			DFS(g, i, visited);
	}
	zero_visited(visited, g->size);
	for (int i = 0; i < g->size; i++) {
		if (!visited[i])
			BFS(g, i, visited);
	}
}

int main() {
	freopen("D:/Develop/GitRepos/MOOC/浙江大学/数据结构/201906/PTA_DS_CN/7_6_d.txt", "r", stdin);
	MGraphT graph(GMAXSIZE);
	resolve(&graph);
	return 0;
}